1. Field of the Invention
The present invention generally concerns data communications systems, in particular internetworking systems and specifically access control techniques for such systems.
2. Description of the Related Art
The data communications field encompasses a wide range of technologies, but systems for connecting networks of computers to other networks, known generally as internetworking, are of increasing importance. As these networks of networks (e.g., the Internet) proliferate, increasing attention is required to the problem of maintaining network security. In particular, access control at the data packet level has become a concern. Also known as packet filtering, packet-level access control is a technique whereby individual data packets in the communications data stream are examined to determine the propriety of accepting, transmitting, or forwarding them. Several different filtering opportunities exist. A packet could be inbound to a xe2x80x9clocalxe2x80x9d computer connected to the switch device (i.e., on the receiving network), inbound but destined to be forwarded to another network, or originating from the local network and destined for another network (outbound). Also, the packet could originate from the local network and be destined for the local network.
FIG. 1 illustrates a high-level schematic view of the operation of a prior art data communications device, such as a router or switch. The device is generally referred to as a xe2x80x9crouter,xe2x80x9d although persons of ordinary skill in the art will recognize that other networked data communications devices may serve an equivalent function.
A number of flows 20, i.e., simultaneous packet- or frame-based messages from multiple sources, are presented to router 10. These flows each consist of multiple packets of data, in a variety of sizes and presented at a variety of rates. Flows may be presented in different protocols, such as the Transmission Control Protocol/Internet Protocol (TCP/IP) and the related User Datagram Protocol (UDP), File Transfer Protocol (FTP), Terminal Emulation Protocol (Telnet), and Hypertext Transfer Protocol (HTTP). Other internetworking protocols are found in the literature, such as Merilee Ford, et. al., Internetworking Technologies Handbook, Cisco Press 1997, (hereinafter Ford) incorporated herein by reference in its entirety. The packets are buffered in a buffer pool 30, which is typically random access memory (RAM). Buffering is accomplished according to the directives of a controller 60 and a buffer manager 25. Controller 60 includes a forwarding engine, not shown, which determines on a packet-by-packet basis the proper destination (xe2x80x9croutingxe2x80x9d) of each packet. This determination is made from information contained within each packet. The flows are sent to the proper output port 70 by way of a set of output queues 40 and a port scheduler 50. Controller 60, buffer manager 25, and port scheduler 50 are conventionally implemented as one or more high speed microprocessors or custom ASICs with associated interface circuitry.
Routers are described in greater detail in Ford, Chapter 5 and Karanjit S. Siyan, Inside TCP/IP, 3d ed., New Riders Publishing 1997 (hereinafter Siyan TCP/IP), incorporated herein by reference in their entirety.
Access control functions in routers and related network communications devices are typically implemented in controller 60 with the co-operation of the forwarding engine. Access controls are discussed generally in Karanjit Siyan and Chris Hare, Internet Firewalls and Network Security, 3d ed., New Riders Publishing 1995 (hereinafter Siyan Firewalls); and D. Brent Chapman and Elizabeth D. Zwicky, Building Internet Firewalls, O""Reilly and Associates, 1995 (hereinafter Chapman). Both Sivan Firewalls and Chapman are incorporated herein by reference in their entirety.
Understanding the background of the present invention requires familiarity with the terminology and organization of modern networking. In particular, an understanding of the functions performed at each layer of the communications hierarchy is required. These functions are generally described by the Open Systems Interconnection (OSI) reference model, well known in the art. See, e.g., Ford, Chapter 1 and Siyan TCP/IP Chapter 2.
An access control list (ACL) is a set of rules for evaluating whether a packet should be permitted to pass or denied routing. As applied to routers, an ACL is implemented as a series of commands that program the router to permit or deny packet access to the routing function. Various classes or families of internetworking devices, such as the Cisco Systems(copyright) Catalyst(copyright) family of switches and the Cisco 7xxx family of routers, respectively, share common command sets and syntax for ACL programming. The command set and syntax used in Cisco routers is more fully described in Network Protocols Configuration Guide. Cisco IOS(copyright) Release 12.0, Cisco Press, 1998, (hereinafter IOS Guide), incorporated herein by reference in its entirety.
The party controlling or maintaining the router (typically, the network administrator) must define the rules by which packet routing is to be controlled. The conventional process of defining these rules is further described in Chapman, Chap. 6 and Siyan Firewalls, Chap. 4. Rule definition is accomplished by commanding the router in accordance with the particular command syntax and programming method appropriate to the type of router used. The router""s operational software (e.g., the Cisco IOS) then translates the access list commands into a form useable by the router. For example, the Cisco family of routers programming syntax is described in the IOS Guide referenced above. The complete Cisco IOS command set is described in further detail in Network Protocols Command Reference, IOS Release 12.0, Cisco Press, 1998 (hereinafter IOS Command Reference), incorporated herein by reference in its entirety.
ACL rules can be simple when expressed in plain English, such as xe2x80x9cPermit TCP packets from any source to host with IP address equal to 194.121.68.173 and TCP port number greater than 1023xe2x80x9d or complex, such as xe2x80x9cPermit UDP packets from any source to host with IP address equal to 142.175.12.40 and TCP port number less than 1023, but not equal to 21, 80, or 128.xe2x80x9d In the first example, the corresponding Cisco IOS router command, for example, contains a single rule element:
permit tcp any host 194.121.68.173 gt 1023
where xe2x80x9cgtxe2x80x9d represents xe2x80x9cgreater than.xe2x80x9d In the latter example, there are four elements to the rule, thus requiring four commands to the router:
deny udp any host 142.175.12.40 eq 21
deny udp any host 142.175.12.40 eq 80
deny udp any host 142.175.12.40 eq 128
permit udp any host 142.175.12.40 lt 1023
Another common rule example is xe2x80x9cDeny TCP traffic going to host with IP address equal to 131.124.87.95 and TCP port number range from 6000 to 6002.xe2x80x9d represented in command form as:
deny tcp any host 131.124.87.95 range 6000 60002
Rules may also be expressed in terms of permitting or denying access to or from certain destination or source IP addresses (respectively), e.g., xe2x80x9cDeny IP traffic coming from subnet 173.201.0.0xe2x80x9d In such situations, the rule command includes the IP address of interest:
deny 173.201.0.0 0.0.255.255
One prior art method used in relatively slow routers required the operational software to interpret the ACL programming commands into a series of conditional statements, such as the well-known software xe2x80x9cCASExe2x80x9d statement. ACL filtering was thus accomplished in software using the interpreted commands directly. This method limited the packet throughput, however, because processing depended on software execution speed.
A faster and more compact method of applying ACL rules is to convert the rule elements into entries in a content-addressable memory (CAM). Content-addressable memories, well-known in the art, allow a simultaneous search of all entries by performing a bit-wise comparison of an input value (the key or comparand) against every entry at the same time. If a match is found between the key and an entry, the CAM returns the address of the matching entry. This address may be used directly by the function requesting the comparison or, more commonly in ACL filtering applications, it may be used as a pointer to a conventional memory array to return another value. In a typical ACL application, the conventional memory contains the action to be taken for a packet whose flow label matches the corresponding CAM entry, such as xe2x80x9cpermitxe2x80x9d or xe2x80x9cdeny.xe2x80x9d (A flow label, also known in the art as a netflow label, contains a series of fields identifying a packet.)
In the context of ACL filtering, CAMs are used to hold bit masks representing elements of the ACL rules. The various rule elements are each implemented by one or more entries in a CAM. For example, the rule element xe2x80x9ceqxe2x80x9d is the simplest CAM entry, because a CAM is designed to test for equivalence between the key and each entry in the CAM. Thus, if the rule is xe2x80x9cdeny packets from port 80,xe2x80x9d the corresponding CAM entry is a bit string representing a value of 80 in the portion of the string corresponding to the port number. Note that, as the rules are typically more complex than simple filters on port numbers, the CAM entries typically consists of multiple fields corresponding to the parts of the conventional flow label of a packet. Such fields typically include the IP source address, IP destination address, source port number, destination port number, type of service (TOS), and Layer 3 and Layer 4 protocol identification. For simplicity, the following examples reflect the portion of the rule element and the corresponding CAM entry corresponding to a single port field (either source or destination). Typical rules filter on more than one flow label field, thus requiring CAM entries many bits wide.
The rule elements are evaluated top to bottom in order to define CAM entries. Their ordering is the sole means by which conflicts between rule elements are resolved, because the typical CAM used for ACL filtering returns the address of only the first matching entry. Thus, a long rule specifying, for example, that packets of a certain Layer 3 protocol (e.g. IP) sent by TCP source port x and destined to destination address a.b.c.d (representing the IP standard dotted-decimal addressing notation) should be permitted, will be first decomposed into its respective elements by the router command interpreter software. The resulting elements are sequenced in the order specified in the rule (in this example, L3 protocol, then TCP source port, then destination address), and the CAM is filled in the order defined by the sequence of rule elements, one rule at a time.
Although one method of filling a CAM is described, those skilled in the art will realize that other methods may be used, such as those requiring additional processing prior to writing the CAM. Accordingly, the invention is not limited to any particular method of filling the CAM.
The rule element lt 6, for example, is implemented in a conventional CAM-based ACL processing system with six entries. Each entry represents a bit mask that matches a port number (either source or destination, as specified in the rule) having any of bits [15:10] set, to wit:
where xe2x80x9c0xe2x80x9d=logic zero and xe2x80x9c1xe2x80x9d=logic one. (Note that this example only shows one of the many fields typically present in a CAM entry as currently used in the art.) If the key matches all bits in an entry, the corresponding action (permit or deny) stored in the memory location pointed to by the address of the matching entry is taken.
Clearly, the more elements in a given rule (i.e., the more complex it is), the more CAM entries required. Fundamentally, a CAM requires an entry, either in width or depth, for each element one wishes to filter access on. Thus, as rule sets increase in complexity, both in terms of number of rules and number of elements within each rule, the CAM needs to grow both wider and deeper. Additional width (i.e., the number of bits in each entry) is required to provide for ANDing of rule elements between different fields in the key. For example, a two-element rule testing for L3 protocol=IP and source address=179.0.0.0 requires testing both the L3 protocol and source address fields. Additional depth is required simply to accommodate all of the rules and rule elements.
FIG. 2 describes the prior art process of ACL filtering. A packet is initially received for access control processing at step 210. In general, this step may be accomplished by dedicated hardware circuitry or software means. A flow label, identifying the packet from its header information and including, for instance, Layer 3 protocol, source, and destination fields, is assembled in step 220. In some prior art implementations, the flow label is already defined elsewhere in the router and serves as an identifier for each packet.
The flow label is used as the key (comparand) for a CAM lookup in step 230. The entire flow label or a subset of its fields may be employed as the key. They key may be created by reordering the flow label as well. Depending on the rule elements loaded into the CAM, the key will either match a CAM entry or not. When a match is found, the CAM returns the address of the matching entry. This address may be used directly as a permit/deny indicator. More commonly, however, the returned address is used as a pointer into an associated memory space, such as a conventional static RAM (SRAM). The SRAM, in one instance an n by 1 bit organization where n is the maximum number of CAM entries, contains a single bit flag for each possible pointer value. The flag indicates xe2x80x9cpermitxe2x80x9d when set and deny when clear. Additional actions are also possible, including forwarding to a CPU.
In the event that the key is not found in the CAM, the default condition, for example, deny, is asserted for the packet. Step 240 consists of reading the SRAM entry pointed to by a successful match in the CAM or denial of access in the default, i.e., when no match is found.
The ACL processing step then loops and waits for the next packet arrival, step 250.
The prior art necessitates a large number of entries for large and complex ACL rule sets. These complex rule sets require multiple entries in a CAM to apply a given complex rule. Modem systems can require thousands of rules. Thus, CAMs for such ACLs rapidly grow to unmanageable depths (i.e. size in terms of number of entries). The power consumed by such CAMs and their cost rapidly become excessive.
Furthermore, the CAM size problem is only exacerbated by the expected shift to Internet Protocol version 6 (IPv6), which uses 128 bit addresses instead of the current 32 bit addresses used by IPv4. This shift requires wider CAMs. For a given size CAM, as the width increases, the depth must correspondingly decrease. This increases sensitivity to ACL entry expansion.
What is needed is a generalized process for pre-computing certain commonly-repeated rule elements and incorporating a xe2x80x9cshorthandxe2x80x9d code (or auxiliary field) representing the results as part of the lookup key so that a match to a single, extended CAM entry (extended by the addition of the shorthand code) will indicate the result of applying a set of rule elements. In this manner, the depth of the CAM needed to implement a given rule can be greatly reduced, thus reducing cost and power consumption. Alternatively, for a given size of CAM, more rules and/or more complex rules can be implemented without increasing the cost of the device.
Cisco Systems, Cisco IOS, and Catalyst are registered trademarks of Cisco Systems, Inc. of San Jose, Calif.
The present invention performs logical operations on fields within the flow label characterizing a received packet or frame of data and uses the results, along with other packet/frame-identifying data, to generate a more efficient content addressable memory (CAM) lookup key. A CAM lookup is used to determine the packet action indicated by the rules defined by a rule-based routing or switching decision process, such as an access control list (ACL). The results of these logical operations extend the key space (i.e., the width of the key) by adding additional fields to the key. This provides a finer-grained match between the original, unextended input key and a rule action contained in the CAM. A fine-grain key match in the CAM thus points to a rule action precisely tailored to packet processing. The rule can thus be applied with fewer CAM entries, providing the rule application versatility improvement and CAM cost reduction necessary to keep up with the ever-increasing rule complexity requirements of advanced data communication and internetworking systems.
Both conventional CAM and ternary content-addressable memories (TCAM) implementations are described. Use of a TCAM for ACL lookups further enhances the efficiency of ACL processing by providing a masking capability for each TCAM entry that can be used to provide an additional level of rule element checking.